<<<<<<< HEAD
package leetcode2;

import java.util.HashMap;
import java.util.Map;
class B {
    public B() {
        // do nothing
        func();
    }
    public void func() {
        System.out.println("B.func()");
    }
}
class D extends B {
    private int num = 1;
    @Override
    public void func() {
        System.out.println("D.func() " + num);
    }
}
public class LeetCodeMain130 {
    public static void main(String[] args) {
        D d = new D();
    }
    //前缀和+哈希表优化 找到该数组中和为 k 的连续子数组的个数
    public int subarraySum(int[] nums, int k) {
        int numCount=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        int pre=0;
        for (int i = 0; i < nums.length; i++) {
            pre+=nums[i];
            if (map.containsKey(pre-k)){
                numCount+=map.get(pre-k);
            }
            map.put(pre,map.getOrDefault(pre,0)+1);
        }
        return numCount;
    }
    //暴力算法 找到该数组中和为 k 的连续子数组的个数
    public int subarraySum2(int[] nums, int k) {
        int numCount=0;
        for (int i = 0; i < nums.length; i++) {
            int sum=nums[i];
            if (sum==k){
                numCount++;
            }
            for (int j = i+1; j < nums.length; j++) {
                sum+=nums[j];
                if (sum==k){
                    numCount++;
                }
            }
        }
        return numCount;
    }
    //数组中和为 k 的个数
    int count=0;
    public int subarraySum1(int[] nums, int k) {
        int sum=0;
        for (int num:nums) {
            sum+=num;
        }
        if (sum<k){
            return 0;
        }else if (sum==k){
            return 1;
        }
        backing(nums,k,0,0);
        return count;
    }
    public void backing(int[] nums,int k,int sum,int startIndex){
        if (k==sum){
            count++;
            return;
        }
        for (int i = startIndex; i < nums.length&&nums[i]+startIndex<=k; i++) {
            sum+=nums[i];
            backing(nums, k, sum, i+1);
            sum-=nums[i];
        }
    }
}
=======
package leetcode2;

public class LeetCodeMain129 {
    //滑动窗口
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int ans=0;
        int l=0;
        int r=0;
        int cur=1;
        while (l<=r&&r<nums.length){
            cur*=nums[r];
            while (l<=r&&cur>=k){
                cur/=nums[l];
                l++;
            }
            ans+=(r-l+1);
            r++;
        }
        return ans;
    }
    //暴力
    public int numSubarrayProductLessThanK1(int[] nums, int k) {
        int maxNum=0;
        for (int i = 0; i < nums.length; i++) {
            int sum=nums[i];
            if (sum<k){
                maxNum++;
            }
            for (int j = i+1; j < nums.length; j++) {
                sum*=nums[j];
                if (sum<k){
                    maxNum++;
                }else {
                    break;
                }
            }
        }
        return maxNum;
    }
}
>>>>>>> e5346752b4e21187c31af6aa8892a487a62be41e
